\documentclass{article}

\usepackage{ctex}
\usepackage{graphicx}
\usepackage{float}
\usepackage{datetime}
\usepackage{listings}

\usepackage{xcolor}
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{ %
	backgroundcolor=\color{white},      % choose the background color
	basicstyle=\footnotesize\yahei,  % size of fonts used for the code
	columns=fullflexible,
	tabsize=4,
	breaklines=true,               % automatic line breaking only at whitespace
	captionpos=b,                  % sets the caption-position to bottom
	commentstyle=\color{mygreen},  % comment style
	escapeinside={\%*}{*)},        % if you want to add LaTeX within your code
	keywordstyle=\color{blue},     % keyword style
	stringstyle=\color{mymauve}\yahei,  % string literal style
	frame=single,
	rulesepcolor=\color{red!20!green!20!blue!20},
	% identifierstyle=\color{red},
	language=c++,
    numbers=left,
    escapeinside=``,
}



\title{Graph Report}
\author{叶睿浩		3190104031}
\date{\today}

\begin{document}
    \maketitle
    这是Graph作业的report

    \section{对图的数据结构的理解}

    对于一个图而言，其基本要素就是节点和边。
    
    存储节点的方式得依照实际的工作环境来进行选择，当需要经常对图进行删改而内存空间又不太充裕的情况下，
    可以通过链表的方式进行存储，这样就可以较为简单的对节点进行增减，但所需的代价也较大，其访问元素所消耗
    的资源为$O (n)$；但如果我们不需要经常性地对图进行删改的话，我们可以考虑将节点以数组的形式进行存储。
    以数组形式存储，意味着我们可以很方便地访问节点元素，但是对节点进行增删的话就比较麻烦。

    存储边的方式也得按照实际工作环境来进行选择，需要注重增删操作时，就要采用链表的模式进行存储；需要注重访问
    元素的操作时，就可以采用数组来进行存储。

    本次作业实现的模板类就做出这样一个关于工作环境的假设：用户在定义图以后不会再新增节点数量。因此我们可以
    考虑用数组的方式来对节点和边进行存储。执行构造函数时，用户必须输入节点数和边数，构造函数会根据边数和
    节点数的关系来决定存储图数据的方式（若用户没有指定存储方法的话）；同时完成图的初始化以后，也就默认
    用户不会新增节点数量，不提供方法用来增加图内的节点数。而有关边的定义是通过方法setEdgeWeight来实现的。
    用户需要通过不断调用setEdgeWeight来新增图内的边，但要想删去某一条边是不被方法所允许的（除非用户知晓
    模板类里实现边的“未定义初始状态”的方法）。

    \section{对Graph模板类的代码说明}

    关于Graph的声明：

    \begin{lstlisting}[language=C++]
        class Graph
        {
        private:
            bool isWeighted;
            bool isDirected;
            int flag; 
            // User should choose adjList or adjMatrix. 
            //adjList, flag=0; 
            //adjMatrix, flag=1; 
            //no choosing, flag=-1

            int numV;
            int numE;
            double **adjMatrix;
            int **adjMatrix_unwt; // unweighted adjacent matrix
    
            int iterator; 
            
            // store the last place where we have created adjList items
            struct Edge_adjList
            {
                int vertex;
                int adjvex;
                double weight;
                Edge_adjList( int vertex, int adjvex, const double & weight ) 
                : vertex{ vertex }, adjvex{ adjvex }, weight{ weight } { }
            };
            Edge_adjList **adjList;
    
            struct Edge_adjList_unwt // unweighted adjacent list
            {
                int vertex;
                int adjvex; 
                int weight;
                Edge_adjList_unwt( int vertex, int adjvex, const int & weight ) 
                : vertex{ vertex }, adjvex{ adjvex }, weight{ weight } { }
            };
            Edge_adjList_unwt **adjList_unwt;
        public:
            Graph( const int _numV, const int _numE, 
            int _flag , bool _isWeighted , bool _isDirected );
            void setEdgeWeight( int tail, int head, double weight ); 
            void setEdgeWeight_unwt( int tail, int head);
            void listVertexes( );
            void listEdges( );
            void wayStoring( ); // print the way of storing the graph
            ~Graph( );
        };
    \end{lstlisting}

    在类中关于节点的定义是依据构造函数中传入的numV来给出的，一旦给出numV就自动生成[0,numV-1]整数数组
    其中每一个数字代表一个节点。

    而关于边的定义，则根据图的存储方式有不同的定义方法。其中flag用于判断存储graph数据的方式，其值默认为-1。
    一旦用户输入flag=0，则以邻接表方式存储；用户输入flag=1，则以邻接矩阵方式存储。若用户未给出flag的输入，
    则根据输入的numV和numE的大小关系来自动选择存储方式：若numV$>$numE则选择邻接表，否则选择邻接矩阵。

    当依照邻接矩阵来进行存储时，构造图时会直接申请numV×numV大小的矩阵数组空间用于存储边的weight，每一条边
    通过访问矩阵元素的方式来进行。如要访问从节点0出发指向节点2的边的weight时，可用adjMatricx[0][2]来获得weight。
    而定义边则是通过setEdgeWeight方法来进行，若没有定义边，则默认在邻接矩阵内部保持未定义的状态。

    当依照邻接表来进行存储时，构造图时会申请numE条边的结构体数组空间用于存放边的weight和两端点信息。每一条边通过
    访问边的编号来进行。如要访问编号为1的边的weight，可用adjList[1].weight来获得。而定义边则是通过setEdgeWeight方法
    来进行，若没有定义边，则邻接表内部不会有任何内容。即结构体指针数组内部所有元素为空指针。

    \section{关于模板类的测试}

    测试函数主要用于测试模板类是否能够正常生成graph对象，并执行其对应的方法。

    测试代码如下：

    \begin{lstlisting}[language=C++]
    int main()
    {
        int numV = 3;
        int numE = 4;
        int flag = 0;
        bool isWeighted = false;
        bool isDirected = false;
        Graph g(numV, numE);
        g.setEdgeWeight(0, 1, 2);
        g.setEdgeWeight_unwt(0, 1);
        g.setEdgeWeight(0, 2, 6);
        g.setEdgeWeight(1, 2, 5);
        g.setEdgeWeight(2, 0, 7);
        g.listEdges( );
        g.listVertexes( );
        g.wayStoring( );
        return 0;
    }
    \end{lstlisting}

    在终端中运行结果如下：

    \begin{lstlisting}
    `使用了错误方法，应该使用setEdgeWeight`
    `边如下： `
    0	( 0, 1, 2 )
    1	( 0, 2, 6 )
    2	( 1, 2, 5 )
    3	( 2, 0, 7 )
    `节点如下： `
    0 1 2 
    `使用邻接矩阵存储`
    \end{lstlisting}

    其中报错代码是由于执行了setEdgeWeight$\_$unwt方法。这个方法用于对无权图进行权重设置（其实就是定义边）。
    一旦程序发现对一个有权图执行该方法就会报错。

    \section{内存泄露检查}

    利用valgrind检查内存泄漏情况，报告如下：

    \begin{lstlisting}
    ==12411== HEAP SUMMARY:
    ==12411==     in use at exit: 0 bytes in 0 blocks
    ==12411==   total heap usage: 6 allocs, 6 frees, 73,824 bytes allocated
    ==12411== 
    ==12411== All heap blocks were freed -- no leaks are possible
    ==12411== 
    ==12411== Use --track-origins=yes to see where uninitialised values come from
    ==12411== For lists of detected and suppressed errors, rerun with: -s
    ==12411== ERROR SUMMARY: 11 errors from 3 contexts (suppressed: 0 from 0)
    \end{lstlisting}

    故没有内存泄漏发生。
\end{document}